package site.wanjiahao.union;

/**
 * Quick Union
 * find O(logn)
 * Union O(logn)
 */
public class UnionFind_QU extends UnionFind{

    public UnionFind_QU(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        checkRange(v);
        // 循环找到最终的父节点，最终父节点v = parents[v]
        while (v != parents[v]) {
            v = parents[v];
        }
        // 找到最终父节点
        return v;
    }

    @Override
    public void union(int v1, int v2) {
       // 将v1元素的父元素置为
        int p1 = find(v1);
        int p2 = find(v2);
        // 两父元素相等，不用进行任何操作
        if (p1 == p2) return;

        parents[p1] = p2;
    }
}
